package uk.org.landeg.euler.problems;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

import uk.org.landeg.euler.PrimeGen;
import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;

public class Problem087 extends AbstractProblem {

	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem087());
		launcher.solve();
	}

	@Override
	public String getDescription() {
		return "How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?";
	}

	@Override
	public Integer getProblemNumber() {
		return 87;
	}

	@Override
	public Object solve() {
		long max = 50000000L;
		long upperLimit = (long)Math.sqrt(max);
		PrimeGen.isPrime(upperLimit);
		Set<Long> primeSet = PrimeGen.getPrimes();
		long primes[] = new long[primeSet.size()];
		ArrayList<Long> squares, cubes, fourths;
		squares = new ArrayList<Long>();
		cubes = new ArrayList<Long>();
		fourths = new ArrayList<Long>();
		
		int id = 0;
		System.out.printf("Added %d primes\n", primes.length);
		for (Long l : primeSet) {
			primes[id++] = l;
		}
		for (Long p : primes) {
			if (p * p < max) {
				squares.add(p * p);
			}
			if (p * p * p < max) {
				cubes.add(p * p * p);
			}
			if (p * p * p * p < max) {
				fourths.add(p * p * p * p);
			}
		}
		System.out.printf("Array sizes %d %d %d\n",squares.size(),cubes.size(),fourths.size());
		HashSet<Long> numbers = new HashSet<Long>();

		for (Long a : fourths) {
			for (Long b: cubes) {
				for (Long c: squares) {
					if (a + b + c < max) {
						numbers.add(a+b+c);
					}
				}
			}
		}
		return numbers.size();
	}
}
